package medium.array;

/**
 * <a href="https://leetcode.cn/problems/sum-in-a-matrix/">2679. 矩阵中的和</a>
 * 给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：
 * 矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
 * 在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数 中。
 * 请你返回最后的 分数 。
 * 示例 1：
 *   输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
 *   输出：15
 *   解释：第一步操作中，我们删除 7 ，6 ，6 和 3 ，将分数增加 7 。下一步操作中，删除 2 ，4 ，5 和 2 ，将分数增加 5 。最后删除 1 ，2 ，3 和 1 ，将分数增加 3 。所以总得分为 7 + 5 + 3 = 15 。
 * 示例 2：
 *   输入：nums = [[1]]
 *   输出：1
 *   解释：我们删除 1 并将分数增加 1 ，所以返回 1 。
 * 提示：
 *   1 <= nums.length <= 300
 *   1 <= nums[i].length <= 500
 *   0 <= nums[i][j] <= 10^3
 * @author 刘学松
 * @date 2023-07-04 9:36
 */
public class 矩阵中的和 {
    /**
     * 用每行元素按从大到小依次进行从右到左填充maxs，大于就覆盖
     * @param nums
     * @return
     */
    public int matrixSum(int[][] nums) {
        int N = nums[0].length;
        // 存放每个位置的最大值
        int[] maxs = new int[N];
        // 用于统计每个元素出现的次数，大小可以根据实际情况调整
        int[] map = new int[1001];

        for (int[] ar : nums) {
            // 当前子数组的最大值
            int maxv = 0;
            for (int v : ar) {
                maxv = Math.max(maxv, v);
                // 统计每个元素出现的次数
                map[v]++;
            }
            // 剩余未填充的位置数量
            int n = N-1;
            // 当前已填充位置的最小值
            int minv = maxs[0];
            // 从最大值开始遍历到已填充位置的最小值
            for (int v = maxv; v > minv && n > 0; v--) {
                // 获取当前值出现的次数
                int c = map[v];
                if (c != 0) {
                    // 将当前值的出现次数清零
                    map[v] = 0;
                    while (c != 0) {
                        // 将当前值填充到剩余位置中
                        // 如果当前位置的值小于当前值，则更新为当前值
                        if (maxs[n] < v) {
                            maxs[n] = v;
                        }
                        --n;
                        --c;
                    }
                }
            }
        }
        // 结果变量，用于存放累加最大值
        int res = 0;
        for (int v : maxs) {
            res += v;
        }

        return res;
    }
}
